Spiral matrix [Simulation, Layer-by-Layer]¶
Time: O(MxN); Space: O(1); medium
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input: matrix =
[
[ 1, 2, 3],
[ 4, 5, 6],
[ 7, 8, 9]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix =
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Hints:
Well for some problems, the best way really is to come up with some algorithms for simulation. Basically, you need to simulate what the problem asks us to do.
We go boundary by boundary and move inwards. That is the essential operation. First row, last column, last row, first column and then we move inwards by 1 and then repeat. That’s all, that is all the simulation that we need.
Think about when you want to switch the progress on one of the indexes. If you progress on i out of [i, j], you’d be shifting in the same column. Similarly, by changing values for j, you’d be shifting in the same row. Also, keep track of the end of a boundary so that you can move inwards and then keep repeating. It’s always best to run the simulation on edge cases like a single column or a single row to see if anything breaks or not.
1. Simulation [O(N), O(N)]¶
Intuition Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would go out of bounds or into a cell that was previously visited.
Algorithm Let the array have R rows and C columns. seen[r][c] denotes that the cell on the r-th row and c-th column was previously visited. Our current position is (r, c), facing direction di, and we want to visit R x C total cells.
As we move through the matrix, our candidate next position is (cr, cc). If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.
[2]:
class Solution1(object):
"""
Simulation
Time: O(N), where N is the total number of elements in the input matrix.
We add every element in the matrix to our final answer.
Space: O(N), the information stored in seen and in ans.
"""
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix:
return []
R, C = len(matrix), len(matrix[0])
seen = [[False] * C for _ in matrix]
ans = []
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
r = c = di = 0
for _ in range(R * C):
ans.append(matrix[r][c])
seen[r][c] = True
cr, cc = r + dr[di], c + dc[di]
if 0 <= cr < R and 0 <= cc < C and not seen[cr][cc]:
r, c = cr, cc
else:
di = (di + 1) % 4
r, c = r + dr[di], c + dc[di]
return ans
[3]:
s = Solution1()
matrix = [
[ 1, 2, 3],
[ 4, 5, 6],
[ 7, 8, 9]
]
assert s.spiralOrder(matrix) == [1,2,3,6,9,8,7,4,5]
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
assert s.spiralOrder(matrix) == [1,2,3,4,8,12,11,10,9,5,6,7]
2. Layer-by-Layer [O(N), O(N)]¶
Intuition The answer will be all the elements in clockwise order from the first-outer layer, followed by the elements from the second-outer layer, and so on.
Algorithm We define the k-th outer layer of a matrix as all elements that have minimum distance to some border equal to k. For example, the following matrix has all elements in the first-outer layer equal to 1, all elements in the second-outer layer equal to 2, and all elements in the third-outer layer equal to 3.
[
[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]
]
For each outer layer, we want to iterate through its elements in clockwise order starting from the top left corner. Suppose the current outer layer has top-left coordinates (r1, c1) and bottom-right coordinates (r2, c2).
Then, the top row is the set of elements (r1, c) for c = c1,…,c2, in that order. The rest of the right side is the set of elements (r, c2) for r = r1+1,…,r2, in that order. Then, if there are four sides to this layer (ie., r1 < r2 and c1 < c2), we iterate through the bottom side and left side as shown in the solutions below.
[4]:
class Solution2(object):
"""
Layer-by-Layer
Time: O(N), where N is the total number of elements in the input matrix.
We add every element in the matrix to our final answer.
Space: O(N), the information stored in ans.
"""
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
def spiral_coords(r1, c1, r2, c2):
for c in range(c1, c2 + 1):
yield r1, c
for r in range(r1 + 1, r2 + 1):
yield r, c2
if r1 < r2 and c1 < c2:
for c in range(c2 - 1, c1, -1):
yield r2, c
for r in range(r2, r1, -1):
yield r, c1
if not matrix: return []
ans = []
r1, r2 = 0, len(matrix) - 1
c1, c2 = 0, len(matrix[0]) - 1
while r1 <= r2 and c1 <= c2:
for r, c in spiral_coords(r1, c1, r2, c2):
ans.append(matrix[r][c])
r1 += 1; r2 -= 1
c1 += 1; c2 -= 1
return ans
[5]:
s = Solution2()
matrix = [
[ 1, 2, 3],
[ 4, 5, 6],
[ 7, 8, 9]
]
assert s.spiralOrder(matrix) == [1,2,3,6,9,8,7,4,5]
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
assert s.spiralOrder(matrix) == [1,2,3,4,8,12,11,10,9,5,6,7]
[8]:
class Solution3(object):
"""
Time: O(M * N)
Space: O(1)
"""
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
result = []
if matrix == []:
return result
left, right, top, bottom = 0, len(matrix[0]) - 1, 0, len(matrix) - 1
while left <= right and top <= bottom:
for j in range(left, right + 1):
result.append(matrix[top][j])
for i in range(top + 1, bottom):
result.append(matrix[i][right])
for j in reversed(range(left, right + 1)):
if top < bottom:
result.append(matrix[bottom][j])
for i in reversed(range(top + 1, bottom)):
if left < right:
result.append(matrix[i][left])
left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
return result
[9]:
s = Solution3()
matrix = [
[ 1, 2, 3],
[ 4, 5, 6],
[ 7, 8, 9]
]
assert s.spiralOrder(matrix) == [1,2,3,6,9,8,7,4,5]
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
assert s.spiralOrder(matrix) == [1,2,3,4,8,12,11,10,9,5,6,7]